Algorithms · 27
Stacks and Queues
A stack hands back the newest item first; a queue hands back the oldest first.
A stack and a queue hold values and give them back in a fixed order.
The example below is a school cafeteria.tray x puts tray number x on top of the pile, and come name puts that person at the back of the line.serve lets the person at the front take the top tray, or prints - if there is no tray or nobody waiting.
At the end it prints how many trays are left and how many people are still waiting.
from collections import deque q = int(input())pile = [] # 스택: 끝이 맨 위waiting = deque() # 큐: 왼쪽이 맨 앞for _ in range(q): parts = input().split() if parts[0] == "tray": pile.append(int(parts[1])) # 맨 위에 올리기 elif parts[0] == "come": waiting.append(parts[1]) # 맨 뒤에 서기 elif pile and waiting: # 꺼내기 전에 비었는지 확인 name = waiting.popleft() # 가장 먼저 온 사람 tray = pile.pop() # 가장 나중에 올린 식판 print(name, tray) else: print("-")print(len(pile), len(waiting))const lines = require("fs").readFileSync(0, "utf8").split("\n");const q = Number(lines[0]);const pile = []; // 스택: 끝이 맨 위const waiting = []; // 큐: 뒤에 넣고, 맨 앞 번호(head)만 뒤로 옮겨요let head = 0;for (let i = 1; i <= q; i++) { const parts = lines[i].trim().split(" "); if (parts[0] === "tray") { pile.push(Number(parts[1])); // 맨 위에 올리기 } else if (parts[0] === "come") { waiting.push(parts[1]); // 맨 뒤에 서기 } else if (pile.length > 0 && head < waiting.length) { // 꺼내기 전에 비었는지 확인 const name = waiting[head++]; // 가장 먼저 온 사람 const tray = pile.pop(); // 가장 나중에 올린 식판 console.log(name, tray); } else { console.log("-"); }}console.log(pile.length, waiting.length - head);import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const q: number = Number(lines[0]);const pile: number[] = []; // 스택: 끝이 맨 위const waiting: string[] = []; // 큐: 뒤에 넣고, 맨 앞 번호(head)만 뒤로 옮겨요let head: number = 0;for (let i = 1; i <= q; i++) { const parts: string[] = lines[i].trim().split(" "); if (parts[0] === "tray") { pile.push(Number(parts[1])); // 맨 위에 올리기 } else if (parts[0] === "come") { waiting.push(parts[1]); // 맨 뒤에 서기 } else if (pile.length > 0 && head < waiting.length) { // 꺼내기 전에 비었는지 확인 const name: string = waiting[head++]; // 가장 먼저 온 사람 const tray = pile.pop(); // 가장 나중에 올린 식판 console.log(name, tray); } else { console.log("-"); }}console.log(pile.length, waiting.length - head);import java.util.ArrayDeque;import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int q = sc.nextInt(); ArrayDeque<Integer> pile = new ArrayDeque<>(); // 스택: push · pop ArrayDeque<String> waiting = new ArrayDeque<>(); // 큐: add · poll for (int i = 0; i < q; i++) { String cmd = sc.next(); if (cmd.equals("tray")) { pile.push(sc.nextInt()); // 맨 위에 올리기 } else if (cmd.equals("come")) { waiting.add(sc.next()); // 맨 뒤에 서기 } else if (!pile.isEmpty() && !waiting.isEmpty()) { // 꺼내기 전에 비었는지 확인 String name = waiting.poll(); // 가장 먼저 온 사람 int tray = pile.pop(); // 가장 나중에 올린 식판 System.out.println(name + " " + tray); } else { System.out.println("-"); } } System.out.println(pile.size() + " " + waiting.size()); }}using System;using System.Collections.Generic; class Program{ static void Main() { int q = int.Parse(Console.ReadLine()); var pile = new Stack<int>(); // 스택: Push · Pop var waiting = new Queue<string>(); // 큐: Enqueue · Dequeue for (int i = 0; i < q; i++) { string[] parts = Console.ReadLine().Trim().Split(' '); if (parts[0] == "tray") { pile.Push(int.Parse(parts[1])); // 맨 위에 올리기 } else if (parts[0] == "come") { waiting.Enqueue(parts[1]); // 맨 뒤에 서기 } else if (pile.Count > 0 && waiting.Count > 0) // 꺼내기 전에 비었는지 확인 { string name = waiting.Dequeue(); // 가장 먼저 온 사람 int tray = pile.Pop(); // 가장 나중에 올린 식판 Console.WriteLine(name + " " + tray); } else { Console.WriteLine("-"); } } Console.WriteLine(pile.Count + " " + waiting.Count); }}#include <iostream>#include <queue>#include <stack>#include <string> int main() { int q; std::cin >> q; std::stack<int> pile; // 스택: push · top · pop std::queue<std::string> waiting; // 큐: push · front · pop for (int i = 0; i < q; i++) { std::string cmd; std::cin >> cmd; if (cmd == "tray") { int x; std::cin >> x; pile.push(x); // 맨 위에 올리기 } else if (cmd == "come") { std::string who; std::cin >> who; waiting.push(who); // 맨 뒤에 서기 } else if (!pile.empty() && !waiting.empty()) { // 꺼내기 전에 비었는지 확인 std::string name = waiting.front(); // 가장 먼저 온 사람 waiting.pop(); // pop은 값을 돌려주지 않아서 먼저 읽고 빼요 int tray = pile.top(); // 가장 나중에 올린 식판 pile.pop(); std::cout << name << ' ' << tray << '\n'; } else { std::cout << "-\n"; } } std::cout << pile.size() << ' ' << waiting.size() << '\n';}#include <stdio.h>#include <string.h> int main(void) { int q; static int pile[1000]; // 스택: top이 든 개수이자 다음에 넣을 자리 int top = 0; static char waiting[1000][11]; // 큐: head가 맨 앞, tail이 다음에 넣을 자리 int head = 0, tail = 0; scanf("%d", &q); for (int i = 0; i < q; i++) { char cmd[8]; scanf("%7s", cmd); if (strcmp(cmd, "tray") == 0) { scanf("%d", &pile[top++]); // 맨 위에 올리기 } else if (strcmp(cmd, "come") == 0) { scanf("%10s", waiting[tail++]); // 맨 뒤에 서기 } else if (top > 0 && head < tail) { // 꺼내기 전에 비었는지 확인 char *name = waiting[head++]; // 가장 먼저 온 사람 int tray = pile[--top]; // 가장 나중에 올린 식판 printf("%s %d\n", name, tray); } else { printf("-\n"); } } printf("%d %d\n", top, tail - head); return 0;}q = Console.ReadLine().ToNumber();pile = []; // 스택: 끝이 맨 위waiting = []; // 큐: 뒤에 넣고, 맨 앞 번호(head)만 뒤로 옮겨요head = 0;for (i = 0; i < q; i++){ parts = Console.ReadLine().Trim().Split(); if (parts[0] == "tray") { pile.Add(parts[1].ToNumber()); // 맨 위에 올리기 } else if (parts[0] == "come") { waiting.Add(parts[1]); // 맨 뒤에 서기 } else if (pile.Count > 0 && head < waiting.Count) { name = waiting[head]; // 가장 먼저 온 사람 head += 1; tray = pile[pile.Count - 1]; // 가장 나중에 올린 식판 pile.RemoveAt(pile.Count - 1); Console.WriteLine(name + " " + tray); } else { Console.WriteLine("-"); }}Console.WriteLine(pile.Count + " " + (waiting.Count - head));9 tray 3 tray 8 come ann come bob serve tray 5 serve serve come cho
ann 8 bob 5 - 1 1
Key points
- A stack gives back the last item put in first (last in, first out: LIFO).
Like a pile of trays, things go in and come out at the same end. - A queue gives back the first item put in first (first in, first out: FIFO).
Like a line of people, things go in at the back and come out at the front. - A stack needs only the end of a list.
Adding at the end and removing from the end moves nothing else. - Removing the front of a list shifts everything left by one place.
Measured on our judge, draining 200,000 items from the front took about 3.5 s with Python'slist.pop(0), about 2 s with Java'sArrayList.remove(0), about 1.7 s with C#'sList.RemoveAt(0)and with C++'svector.erase(begin()), and JavaScript'sshift()took a little over 3 seconds and hit the 3-second limit.
The same job with a real queue (deque,ArrayDeque,Queue,std::queue) finished within 0.05 s in every case, program start-up included. - JavaScript, TypeScript, C and Craykon have no built-in queue, so use an array (list) as the queue.
Add at the end; to take, do not remove anything: readwaiting[head]and then move the front indexheadforward by one.
The queue is empty whenheadequals the number of items added, and the number waiting isitems added − head.
On our judge, taking 200,000 items this way in JavaScript took less than 0.01 s. - Check for empty before taking. Taking from an empty stack or queue stops with an error in some languages (Python, C#, Craykon) and quietly hands you
undefinedornullin others (JavaScript, Java'spoll).
In C and C++ nothing is promised about what happens.
How each language writes it
| Python | A stack is a list: pile.append(x), pile.pop(), look at the top with pile[-1].A queue is from collections import deque: waiting.append(x), waiting.popleft(), look at the front with waiting[0].Empty check: if pile:.Taking from an empty one raises IndexError.queue.Queue is meant for passing values between threads, and its get() waits forever on an empty queue instead of raising an error, so use deque here |
|---|---|
| JavaScript | A stack is an array: pile.push(x), pile.pop(), look at the top with pile[pile.length - 1].There is no queue type, so add with waiting.push(x) and take with waiting[head++].pop() and shift() on an empty array give undefined with no error |
| TypeScript | Same as JavaScript. The type of pile.pop() is number | undefined, so to store it in a number variable, check for empty and then write pile.pop()! |
| Java | Both are ArrayDeque.Stack: push, pop, peek.Queue: add, poll, peek.push adds at the front and add at the back, while pop, poll and peek all work on the front.Empty check: isEmpty().On an empty one pop() throws NoSuchElementException, while poll() and peek() return null |
| C# | Stack<int>: Push, Pop, Peek.Queue<string>: Enqueue, Dequeue, Peek.The size is Count.Taking from an empty one throws InvalidOperationException; TryPop(out x) and TryDequeue(out x) return false instead of stopping |
| C++ | #include <stack>: push, top, pop.#include <queue>: push, front, pop.pop() returns nothing, so read with top() or front() first.Empty check: empty().Calling top(), front() or pop() on an empty one is not guaranteed to stop with an error; nothing is promised about what happens (undefined behaviour) |
| C | There is no ready-made type, so use an array and indexes. Stack: add with pile[top++] = x;, take with pile[--top].Queue: add at waiting[tail++], take from waiting[head++].Not empty means top > 0 and head < tail |
| Craykon | Both are lists. Stack: pile.Add(x), the top is pile[pile.Count - 1], remove it with pile.RemoveAt(pile.Count - 1).Queue: add with waiting.Add(x), read waiting[head], then head += 1.Reading or removing from an empty list stops with "list is empty" |
Common mistakes
Taking from an empty stack without any errorJavaScript
const pile = [];
const tray = pile.pop();
console.log(tray + 1);→ NaN — pop() on an empty array does not stop; it gives undefined, and the wrong value quietly flows into the calculation
Check pile.length > 0 before taking.
TypeScript rejects the same code before it runs with 'tray' is possibly 'undefined'.
Adding with add and taking with popJava
Deque<Integer> pile = new ArrayDeque<>();
pile.add(1);
pile.add(2);
pile.add(3);
System.out.println(pile.pop());→ 1 — not the 3 that went in last. add puts items at the very back and pop takes from the very front, so it behaved like a queue
Use matching pairs: push and pop for a stack, add and poll for a queue.push adds at the front, so after pushing 1, 2, 3 with push, pop() gives 3.
Expecting pop() to return the valueC++
std::stack<int> pile;
pile.push(3);
int tray = pile.pop();→ Compile error void value not ignored as it ought to be — pop() on std::stack and std::queue only removes and returns nothing
Read first with int tray = pile.top();, then remove with pile.pop();.
For a queue, read with front().
How languages differ
Work that handles "the most recent first" (undo, matching brackets) is a stack; work that handles things "in arrival order" (lines, waiting for a turn) is a queue.
A queue that only moves
Craykon lists hold at most 10,000 items, and draining 10,000 from the front with
Work that handles "the most recent first" (undo, matching brackets) is a stack; work that handles things "in arrival order" (lines, waiting for a turn) is a queue.
A queue that only moves
head keeps the taken values in the array, so in C size the array for the number of insertions, not for the most that wait at once.Craykon lists hold at most 10,000 items, and draining 10,000 from the front with
RemoveAt(0) still finished within 0.2 s on our judge.