Stack & Queue

Stack

LIFO (Last In First Out)

 0  1  2
[4, 7, 8]

| 8 | 2
| 7 | 1
|_4_| 0

Declare

Python

s = []

Java

import java.util.Stack;

Stack<Integer> variable = new Stack<Integer>();

C++

#include <stack>
using namespace std;

stack<int> s;

Add elements

Python

s = []
s.push(1)

Java

Stack<Integer> s = new Stack<Integer>();
s.push(1);

C++

stack<int> s;
s.push(1);

Delete last (most above) element

Python

value = s.pop();

Java

int value = s.pop();

C++

s.pop();  // note that this doesn't return popped value

Get value of last (most above) element

Python

value = s[-1]

Java

int value = s.peek();

C++

int value = s.top();

Get stack's size

Python

n = len(s)

Java

int n = s.size();

C++

int n = s.size();

Check if stack is empty

Python

if len(s) == 0:
  # statement

Java

if( s.empty() )
  // statement

C++

if( s.empt() == true)
  // statement

Swap 2 stacks

Python

s1, s2 = s2, s1

Java

Stack<Integer> temp = s1;
s1 = s2;
s2 = temp;

C++

s1.swap(s2);

Queue

FIFO (First In First Out)

   _________
=>  4 3 2 1  =>
   ---------

Một lợi thế queue so với stack là về mặt bộ nhớ. Queue có thể implement bằng linked list nên nằm rời rạc ở các vùng nhớ được $\rightarrow$ tận dụng được vùng nhớ phân mảnh.

Declare

Python

# There are many types like LIFO Queue, Queue, Priority Queue. So we need to
# import correct one.

# Python 2
import Queue
q = Queue.Queue()

# Python 3
import queue
q = queue.Queue()

# My favorite, only import what you need
from queue import Queue
q = Queue()

Java

// Queue in Java is just interface (no memory located) -> so we implement it using LinkedList
import java.util.LinkedList;
import java.util.Queue;

Queue<Integer> q = new LinkedList<Integer>();

C++

#include <queue>
using namespace std;

queue<int> q;

EnQueue (add element)

Python

q.put(1)

Java

q.add(1);
q.offer(2);

C++

q.push(1);

Deque (delete element)

Delete here means remove the first element. Since queue is FIFO, we can only delete the first element. So we don't have pop() method like stack (get the last element).

Python

value = q.get()

Java

int value = q.remove();

C++

q.pop();  // doesn't return value

Get value of the first element

Python

# Trick with Python, since queue is implemented using list.
value = q.queue[0]

Java

int value = q.peek();

C++

int value = q.front();

Get queue's size

Python

n = q.qsize()

Java

int n = q.size();

C++

int n = q.size();

Check if queue is empty

Python

if q.empty():
  # statement

Java

if( q.isEmpty() )
  // statement

C++

if( q.empty() == true )
  // statement

Swap 2 queues

Python

q1, q2 = q2, q1

Java

Queue<Integer> temp = q1;
q1 = q2;
q2 = temp;

C++

q1.swap(q2);

Deque (double ended queue)

Deque thì thay vì như queue là thêm cuối lấy đầu thì dequeue có thể thêm lấy ở cả 2 đầu. Có thể nói là sự kết hợp giữa stack và queue.

Python

Java

C++

Compare complexity

Ứng dụng của stack và queue

Lưu trữ và cơ chế hoạt động. Cơ chế hoạt động của đệ quy là stack (gọi dần xuống dưới, tới dưới cùng làm xong thì quay ngược lại)

$\rightarrow$ Khử đệ quy thì dùng stack để lưu trữ function, info (vì dùng đệ quy phải tốn chi phí tạo lại function).