Stacks, Explained | Data Structures and Algorithms

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 10.1 Free with a free account

Stacks

Data Structures and Algorithms · Chapter 10: Stacks, Queues, and DequesSection 10.1 · lesson 39 of 879 min · free with a free account

← Doubling the Search Range Until the Target Is FoundNext lesson: Processing the Earliest Added Element First →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

Last-in, first-out stacks with arrays, linked nodes, and ArrayDeque.

  • Describe the stack abstract data type and its LIFO rule
  • Implement array-based and linked stacks with constant-time push and pop
  • Choose overflow and underflow policies in advance
  • Explain why Java code should use a Deque instead of the legacy Stack class

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,322 words). Read along, or search it.

Opening Question

A Stack of Cafeteria Plates

A stack of plates in a cafeteria has a simple rule. You add a clean plate to the top, and you take one from the top. The plate placed most recently is the first one removed, and the plate at the bottom waits longest. That's last in, first out, or LIFO. You've met one already: the call stack, with one frame per active method call. The most recent call always finishes first. Java even has a class named Stack. By the end of this lesson, you'll see why everyday code shouldn't use it.

Definition

The Stack Abstract Data Type

As an abstract data type, a stack is described by what it does, not by how it stores things. Every operation works at one end, the top. Push places a value on the top. Pop removes the top value and returns it. Peek returns it without removing it. And is empty asks whether anything's there. A size operation is common too. But what's missing matters more: there's no way to reach the middle, or remove from underneath. Because only the top is reachable, values always come out in the reverse of the order they went in.

Implementation

An Array with a Size Counter

The simplest design keeps the values in an array, with a counter called size. The bottom of the stack sits at index zero. The top is at index size minus one, and size itself marks the next free slot. Push writes the value at index size, then adds one to size. A full array throws an exception instead. Pop does the reverse. It takes one from size, then returns the value at that index. And peek returns the value at size minus one, without changing anything.

Worked Example

Pop Never Erases Anything

Notice that pop never erases anything. Once size moves back, the old value is outside the live part of the array, and the next push will overwrite it. Each operation does a fixed amount of work, so push, pop, peek and is empty are all order one. Now run main. It checks is empty, pushes four, nine and seven, peeks, pops twice, and peeks again. Seven comes off first, then nine, and four is left on top, exactly as the rule promises.

Quick Check

Printing the Whole Backing Array

Quick check. This main pushes four, nine and seven onto a stack of capacity four. Then it pops twice, and pushes three. Finally it prints the whole array, live part or not. What does it print? Pause and predict. It prints four, three, seven, zero. The two pops only moved size back to one; nothing was erased. So pushing three overwrote nine at index one. Seven still sits at index two, outside the live part, and the never-used last slot keeps Java's default, zero. Four, three, zero, zero assumes pop clears its slot. It doesn't need to: only size decides what's live. And four, nine, seven, three forgets that the pops happened at all.

Error Handling

Overflow and Underflow Policies

A stack can fail in two ways. Overflow is a push onto a stack with no room. Underflow is a pop or a peek on an empty stack. Good code decides in advance how each is handled, instead of leaving it to chance. For overflow, a fixed array can throw an exception, grow the array, or report failure, say by returning false. Then the caller must check every time. For underflow, an exception makes the mistake impossible to ignore. A special value like null is convenient, but it must never be a real element. And with either policy, checking is empty first is good practice.

Worked Example

Pushing onto a Full Stack

Here's the throwing policy in action. A stack of capacity three gets pushes of ten, twenty, thirty and forty. Three pushes succeed. The fourth finds size equal to the length, and the program stops with an illegal state exception. The stack trace names the push method first, and then main, the line that called it.

Worked Example

Popping an Empty Stack

Underflow looks similar. Push five, pop it, and then pop again from the empty stack. The first pop prints five. The second throws an empty stack exception, with no message, and the stack trace points at pop. Either way, the policy was decided in advance, so the failure is loud, and easy to find.

Growth

Doubling the Array When Full

To avoid overflow, the stack can grow instead. When the array is full, push allocates one twice as large, copies the values across, and carries on. This version starts at capacity two. It grows on the third push, and again on the fifth. Most pushes are order one. The push that triggers growth copies every element, so that one costs order n. Doubling keeps those copies rare, so on average, pushes stay cheap.

Implementation

A Stack of Linked Nodes

A stack can also be built from linked nodes. Each node holds a value, and a reference to the node beneath it. One reference, top, points at the newest node. Adding and removing at the front of a singly linked list takes constant time, so the front is the natural top. Push makes a new node that points at the old top, and moves top to it. Pop reads top's value, then moves top down one node. Push four, nine and seven, then pop three times: seven, nine, four. A fourth pop throws the same exception as before.

Comparison

Array Stack Versus Linked Stack

Both designs give order one push, pop and peek. They differ elsewhere. An array stack has a fixed capacity, unless you make it grow. A linked stack is limited only by memory, so overflow is practically not an issue. An array stores just the value per element. Each node also carries a reference. And an array stack copies occasionally as it grows, while a linked stack allocates one small node on every push.

Java Library

Why Not the Legacy Stack Class

So which stack should everyday Java code use? Java's library has a class named Stack, but it dates from the earliest versions of the language. It's built on Vector, an old growable array, so a Stack carries every Vector operation, including reading or inserting at any index. The Java documentation itself recommends a Deque instead, usually an ArrayDeque. This program pushes one, two and three onto each. The deque prints top first. The legacy stack prints bottom first. Get of zero returns one, the bottom, and adding ninety-nine at index one slips it into the middle. That breaks the stack's promise. And on an empty ArrayDeque, peek returns null, while pop throws a no such element exception.

Best Practice

Use a Deque Backed by ArrayDeque

Declaring the variable as a Deque exposes the operations a stack needs, though a Deque offers a little more than that. Two cautions with ArrayDeque. It rejects null elements, and peek on an empty deque returns null rather than throwing. So check is empty first if you want an exception. In practice: in application code, write a Deque backed by an ArrayDeque. To learn how stacks work, build your own, as here. And avoid the legacy Stack in new code.

Quick Check

Printing a Deque Used as a Stack

One more check. A deque used as a stack gets pushes of two, eight and five. Then one pop, and a push of six. What does printing the deque show? Pause and predict. It prints six, eight, two. The pop removed five, the top at that moment, and six then went on top of eight. An ArrayDeque prints from the top down, so six comes first. Two, eight, six is the legacy Stack's bottom-first habit, and the third option forgets the pop.

Key Takeaways

Stack Essentials

To sum up. A stack is last in, first out, and only the top can be reached. Push, pop, peek and is empty are order one, in both the array and the linked design. An array stack must choose an overflow policy: throw, grow, or report. Every stack must handle underflow. And in Java, use a Deque backed by an ArrayDeque, not the legacy Stack.

Think About It

Pushing at Index Zero

Something to think about. A teammate suggests pushing at index zero, and shifting every other value one place right to make room. Would the stack still behave correctly? What would happen to the cost of push and pop, and why is the end of the array a better top?

About Data Structures and Algorithms at UPI Study

Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms

Why take it here

Why students take Data Structures and Algorithms with UPI Study

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Stacks

What is a stack data structure?
A stack is a last-in, first-out (LIFO) collection in which every operation works at one end, the top. Push adds a value to the top, pop removes and returns the top value, peek returns it without removing it, and isEmpty checks whether anything is there. There is no access to the middle, so values come out in the reverse of the order they went in.
How do you implement a stack with an array in Java?
Keep the values in an array with a size counter, so the bottom is at index 0 and the top at index size - 1. Push runs data[size++] = value, and pop returns data[--size]. Both are O(1). For an int array, pop does not need to erase the slot, because size alone decides which part is live. A full array should throw, grow, or report failure.
Should you use the Stack class in Java?
No, new Java code should use a Deque, usually an ArrayDeque, instead of the legacy Stack class, as the Java documentation recommends. Stack is built on Vector, so it also allows reading or inserting at any index, which breaks the stack's rule. Write Deque<Integer> stack = new ArrayDeque<>(); and use push, pop, and peek. ArrayDeque rejects null elements, and its peek returns null when empty.
What is the difference between stack overflow and underflow?
Overflow is a push onto a stack with no room, and underflow is a pop or peek on an empty stack. A fixed-size array stack must choose an overflow policy in advance: throw an exception, grow the array, or report failure by returning false. For underflow, throwing an exception makes the mistake impossible to ignore. A linked stack is limited only by memory, so overflow is practically not an issue.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Data Structures and Algorithms.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →