Difficulty: Beginner to Intermediate | Prerequisites: Basic C programming, arrays, pointers, linked list fundamentals.
Stacks and queues are the two foundational linear data structures you will use throughout computer science, and COP 3502C treats them as a gateway to more complex structures like trees and graphs. Both restrict how you add and remove elements, and that restriction is the whole point: it enforces an ordering guarantee your program can rely on. If you are comfortable with arrays and singly linked lists in C, you have everything you need to follow this material. If pointers still feel shaky, revisit those notes first.
A stack removes elements in reverse order (last in, first out). A queue removes elements in the order they arrived (first in, first out). Both can be implemented with either arrays or linked lists in C, and the choice affects time complexity for access but not for insertion or removal at the designated ends.
Stack
A linear data structure that follows last-in-first-out (LIFO) ordering. The most recently added element is the first one removed. Think of it as a stack of plates: you always take the top plate off first.
Queue
A linear data structure that follows first-in-first-out (FIFO) ordering. The earliest added element is the first one removed. Think of it as a queue of people at a ticket window: whoever arrived first gets served first.
LIFO (last in, first out)
The removal policy of a stack. The element added most recently is the one that comes off next. In simple terms, the newest item leaves first.
FIFO (first in, first out)
The removal policy of a queue. The element added earliest is the one that comes off next. In simple terms, the oldest item leaves first.
Push
The operation that adds an element to the top of a stack.
Pop
The operation that removes (and typically returns) the element from the top of a stack.
Enqueue
The operation that adds an element to the back (tail) of a queue.
Dequeue
The operation that removes (and typically returns) the element from the front (head) of a queue.
Head pointer
A pointer (or index) that tracks the front of the data structure, where elements are removed in a queue or a stack implemented with two pointers.
Tail pointer
A pointer (or index) that tracks the back of the data structure, where new elements are inserted.
Static array
A fixed-size array declared at compile time. Used for stack and queue implementations where the maximum capacity is known in advance.
Dynamic array
An array that can grow or shrink at runtime (typically via malloc/realloc in C). Useful when the number of elements is unpredictable.
Singly linked list
A chain of nodes where each node holds a value and a pointer to the next node. Supports O(1) insertion and deletion at either end when head and tail pointers are maintained.
The core difference is removal order. A stack uses LIFO; a queue uses FIFO.
Both are linear (not hierarchical, not random-access by design). They impose discipline on the order of element access.
All other differences in implementation flow from this single ordering rule.
Use a static array with a fixed size.
Maintain head and tail pointers (or a single "top" index) to track where the next push goes and where the next pop comes from.
Push increments the top pointer and writes the value. Pop reads the value and decrements the top pointer.
No resizing is needed, so operations are simple and fast, but you must decide the maximum size up front.
Use a dynamic array (allocated with malloc, resized with realloc) so the stack can grow as needed.
Implement push and pop using insert and remove functions that manage the end of the array.
The trade-off: you avoid a fixed capacity limit, but occasional resizes carry an amortised cost.
Use a singly linked list with head and tail pointers.
Push creates a new node and updates the head (or tail, depending on your convention). Pop removes the node at the same end.
No resizing, no wasted memory for unused slots. Each node is allocated individually.
Use a static array with a fixed size.
Maintain head and tail pointers. Enqueue writes at the tail and advances it; dequeue reads at the head and advances it.
A circular buffer approach (wrapping the pointers around to the start of the array) avoids wasting space as elements are dequeued.
Use a singly linked list with head and tail pointers.
Enqueue appends a new node at the tail. Dequeue removes the node at the head.
Both operations are O(1) because you always operate at the ends and maintain direct pointers to both.
Access by index: O(1), because arrays provide constant-time random access.
Push / pop at the top: O(1).
Insert at the end (push): O(1), provided you maintain a tail pointer.
Access by index: O(n), because you must traverse node by node.
Insert at the end (enqueue): O(1), with a tail pointer.
Access by index: O(n), because linked lists do not support random access.
Enqueue / dequeue: O(1) with head and tail pointers (especially in a circular buffer).
Access by index: O(1), inheriting the array's constant-time indexing.
No complex formulas for this topic, but keep these mental models handy:
Stack (array): visualise a vertical list where "top" is the only access point. top index starts at -1 (empty) and increments on push.
Queue (circular buffer): visualise the array as a ring. head chases tail around the circle. The queue is full when (tail + 1) % capacity == head.
Linked list nodes: each node is a box with two fields, data and next. Head and tail are external pointers into the chain.
Stacks underpin function call management (the call stack), undo/redo systems in text editors, and expression evaluation in compilers (e.g. converting infix to postfix notation). Queues are the backbone of task scheduling in operating systems, print spooling, and breadth-first search in graph algorithms.
Students often confuse LIFO and FIFO, especially under time pressure. Remember: stack = LIFO (last in, first out), queue = FIFO (first in, first out). If you mix these up on an exam, every follow-up answer will be wrong.
Students sometimes think a stack needs both a head and a tail pointer. A simple array-based stack only needs a single "top" index. Two pointers are more typical of queues or linked-list implementations.
Students assume linked list access is O(1) because insertion is O(1). Insertion at a known end is O(1); accessing an arbitrary index still requires traversal, so it is O(n).
Students forget that "dynamic array" and "linked list" are different structures. A dynamic array is still contiguous memory (with resizing); a linked list is a chain of individually allocated nodes.
⚠️ The LIFO vs. FIFO distinction is the single most commonly tested concept. Expect at least one question that tries to swap the definitions.
⚠️ Know which data structure (array or linked list) gives O(1) random access and which gives O(n). This appears in time-complexity questions for both stacks and queues.
⚠️ Implementation questions in C like to mix up static arrays, dynamic arrays, and linked lists with incorrect operation names (e.g. "append and delete" instead of "push and pop"). Read the options carefully; the correct answer pairs the right data structure with the right operation mechanism.
⚠️ For linked-list-based queues and stacks, the key detail is maintaining both head and tail pointers. Without the tail pointer, enqueue (or push at the tail) becomes O(n).
True or false: A queue removes elements in the reverse order they were added.
False. A queue uses FIFO, removing elements in the same order they were added.
Fill in the blank: Accessing an element at index i in an array-based stack is ______ time.
O(1).
True or false: A singly linked list requires O(n) time to insert at the tail if you do not maintain a tail pointer.
True. Without a tail pointer, you must traverse the entire list to find the end.
Fill in the blank: The two core operations on a queue are called ______ and ______.
Enqueue and dequeue.
True or false: A static array-based stack can grow indefinitely as you push more elements.
False. A static array has a fixed size determined at compile time.
Q: What is the main difference between a stack and a queue?
A: A stack is LIFO (last in, first out) and a queue is FIFO (first in, first out). The difference is the order in which elements are removed.
Q: How do you implement a stack using a static array in C?
A: Declare a fixed-size array and use a top-of-stack index (or head/tail pointers). Push writes to the current top position and increments the index; pop decrements the index and reads the value.
Q: What is the time complexity of accessing element at index i in a linked-list-based queue?
A: O(n). Linked lists do not support constant-time random access; you must traverse from the head node by node.
Q: What is the time complexity of inserting an element at the end of a linked-list-based queue?
A: O(1), provided you maintain a tail pointer. You simply create a new node and point the current tail's next pointer to it, then update the tail.
Q: When would you choose a dynamic array over a static array for a stack?
A: When you do not know the maximum number of elements in advance. A dynamic array can resize as needed, avoiding the fixed-capacity limitation of a static array, at the cost of occasional reallocation.
Q: In a linked-list implementation of a stack, why do you need head and tail pointers?
A: To achieve O(1) push and pop. The tail pointer lets you insert at one end in constant time, and the head pointer lets you remove from the other end (or the same end, depending on convention) in constant time, without traversing the list.
This material connects directly to recursion (each recursive call pushes a frame onto the call stack, and each return pops one off). It also sets the stage for tree and graph traversal: depth-first search uses a stack, breadth-first search uses a queue. Understanding array vs. linked-list trade-offs here will carry forward to every data structure in COP 3502C and beyond.
stack, queue, LIFO, FIFO, last in first out, first in first out, push, pop, enqueue, dequeue, array-based stack, linked list stack, array-based queue, linked list queue, circular buffer, circular queue, head pointer, tail pointer, top of stack, singly linked list, dynamic array, static array, COP 3502C, Computer Science I, UCF, data structures in C, stack implementation C, queue implementation C, stack vs queue, time complexity stack, time complexity queue, O(1) access, O(n) access