Implementing a Stack, Explained with Code Examples

UPI Study › Courses › Programming in C › Free lessons › Lesson 11.4 Free with a free account

Implementing a Stack

Programming in C · Chapter 11: Dynamic Memory, Linked Lists, Stacks, and QueuesSection 11.4 · lesson 74 of 786 min · free with a free account

← Releasing Memory and Avoiding LeaksNext lesson: Implementing a Queue →

Earn 3 college credits for Programming in CRecommended for credit by NCCRS · Computer Science 240 · self-paced · one payment, lifetime access
Enroll in Programming in C · $250 →Download the syllabus (PDF)

In this lesson

Building a LIFO stack with an array and with linked nodes.

  • Explain the LIFO rule and the push, pop, and peek operations
  • Implement an array stack that checks for overflow and underflow
  • Implement a linked stack that pushes and pops at the front of a list
  • Apply a stack to an undo history and to reversing a sequence

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 (919 words). Read along, or search it.

Opening Question

Plates, Undo, and the Call Stack

At the arcade snack bar, clean plates sit in a stack. You put a plate on top, and the next customer takes the top plate too. Nobody pulls from the bottom. The last plate in is the first one out. That simple rule powers the Undo button in your favorite apps, and the call stack you met in 6.1. In this lesson, you'll build a stack twice: once with an array, and once with linked nodes.

Definition

Last In, First Out

A stack lets you add or remove at one end only, called the top. The rule is called LIFO: last in, first out. It has three operations. push puts a new item on top. pop removes the top item, and hands it back. peek looks at the top item, without removing it. Push 10, 20, then 30, and they come out as 30, 20, 10: the reverse of the order they went in. A good stack guards against two failures. Overflow is pushing when there's no room left. Underflow is popping, or peeking, at an empty stack.

Array Version

An Array Plus a Top Counter

The simplest stack is an array plus one number, top. Here, top says how many items are stored. That also makes top the index of the next free spot. Empty means top is zero. Full means top equals CAPACITY, which is three here. push checks for overflow first. If there's room, it writes at items of top, and then adds one: top plus plus. pop checks for underflow first. Then it subtracts one, minus minus top, and reads that item. peek reads the item just below top, but leaves top alone. push and pop return one for worked, and zero for refused. pop hands the value back through a pointer, as in 6.5, so a refusal never invents a fake number. In main, Sam pushes four values into a stack that holds three. Build and run. 10, 20 and 30 go in. The push of 40 is refused: stack is full. peek shows 30 on top. The pops come back in reverse: 30, 20, 10. And the fourth pop is refused too. Skip those checks, and push writes past the end of the array, while pop reads items of minus one. Both are undefined behavior, as in 7.1.

Quick Check

A Refused Push Leaves 2 on Top

Quick check. The same array stack, with room for three. main pushes 5, 8, 2, and then 7. Then it pops twice, and prints each value. What does it print? Pause and predict. Build and run: 2, then 8. The push of 7 was refused, because the stack already held three items. So 2 stayed on top. The first pop returns 2, and the second returns 8. And 5 is still at the bottom.

Linked Version

The List Front Is the Top

An array stack has a fixed limit. A linked stack has none, because every push gets its own node from the heap. The trick is to use the front of the list as the top. There's no walking to the end, unlike append in 11.1. To push 500, the new node points at the old top, 400. Then top moves to the new node. To pop, save the next node, free the top, and move top to the saved node.

Code Walkthrough

Pushing and Popping Heap Nodes

Here's the linked stack. push gets a node from malloc. If that fails, it returns the old top, so the stack is unchanged. Otherwise, n arrow next gets the old top, and push returns n as the new top. pop checks for underflow: an empty stack is a NULL top. Then it copies the value out, saves the next node in after, frees the top, and returns after. main pushes 100 through 500, then pops until the stack is empty. Build and run: 500, 400, 300, 200, 100. Five values came out in reverse, and each node was freed as it was popped.

Real Use

An Undo History as a Stack

Every editor's Undo button is a stack. Each action is pushed, and Undo pops the most recent one. Sam once deleted a player by mistake, and asked Priya: can I get her back? A stack is all it takes. Here, each Action holds its text, and a pointer called below: the action done just before it. do_action pushes, and undo pops, printing what it undoes. On an empty history, undo prints a message instead. main does three actions and undoes two. Then it adds player Dev, undoes everything, and tries one extra undo. Build and run. Three actions are done. Then delete player Leo and give 50 tokens are undone, newest first. add player Dev goes on top of what was left. Undoing everything then removes Dev, and then Mira. And the extra undo, on an empty history, prints nothing to undo, instead of crashing. That's the underflow check, doing its job.

Quick Check

STAR Comes Out Reversed

Quick check. This program pushes the letters of STAR onto a linked stack, one at a time, S first. Then it pops until the stack is empty, printing each letter. What word comes out? Pause and predict. Build and run: RATS. The last letter pushed, R, is the first one out. Then A, T, and finally S, which was pushed first. A stack always hands things back in reverse order. That's why reversing a word is a classic job for a stack.

Key Takeaways

Push, Pop, and Peek at the Top

To sum up. A stack is last in, first out: push, pop and peek, all at the top. An array stack checks top for overflow and underflow on every push and pop. A linked stack pushes at the front: the new node points at the old top. And pop saves next, frees the top, and moves on.

About Programming in C at UPI Study

Programming in C (Computer Science 240) is a self-paced online course of 78 video lessons in 11 chapters, from pseudocode and your first program to data types, decisions, loops, functions, arrays, strings, pointers, files, structures, dynamic memory and linked lists. 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: C vs C++

Why take it here

Why students take Programming in C with UPI Study

How programs work close to the machineProgramming in C teaches how a program uses memory: variables and data types, control flow, functions, arrays and strings, pointers, files, structures and dynamic memory. C is the base for operating systems, embedded devices and many computer-science courses.
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

Programming in C 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 Implementing a Stack

What is a stack data structure?
A stack is a collection where items are added and removed at one end only, called the top, following the rule last in, first out, or LIFO. push adds an item on top, pop removes and returns the top item, and peek reads it without removing it. Pushing 10, 20, and 30 and then popping three times returns 30, 20, and 10.
How do you implement a stack with an array in C?
Use an array plus an int top that counts the items and also marks the next free slot. push checks that top is below the capacity, then stores items[top] and increments top. pop checks that top is above zero, then decrements top and reads items[top]. peek reads items[top - 1] without changing top. Returning 1 or 0 reports whether each operation worked.
What are stack overflow and stack underflow?
Overflow is pushing onto a stack that has no room left, and underflow is popping or peeking at an empty stack. In an array stack, an unchecked overflow writes past the end of the array, and an unchecked underflow reads items[-1]; both are undefined behavior. Checking top before every push and pop lets the program refuse the operation and report it instead.
How do you implement a stack with a linked list in C?
Treat the front of the list as the top, so no walking is needed. To push, allocate a node, set its next to the old top, and make it the new top. To pop, check for a NULL top, copy the value out, save top->next, free the old top, and move top to the saved node. Unlike an array stack, it has no fixed capacity.

About the Programming in C course

How many college credits is Programming in C?
Programming in C (Computer Science 240) 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 Programming in C cost and what is included?
$250, paid once, with lifetime access: all 78 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 Programming in C take?
It is self-paced with no deadlines. The 78 lessons total about 9 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 Programming in C.

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

Enroll in Programming in C →Download the syllabusEvery course with PRO →
Programming in C
3 credits · NCCRSEnroll →