Adding and Removing at Both Ends of a Sequence, Explained

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

Adding and Removing at Both Ends of a Sequence

Data Structures and Algorithms · Chapter 10: Stacks, Queues, and DequesSection 10.3 · lesson 41 of 8710 min · free with a free account

← Processing the Earliest Added Element FirstNext lesson: Stack Applications: Expressions, Undo and Call Tracking →

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

Double-ended queues with linked nodes, circular arrays, and ArrayDeque.

  • Describe the deque operations at the first and last ends
  • Implement a deque as a doubly linked list with sentinels and as a circular array
  • Explain why doubling the array makes deque adds amortized constant time
  • Use Java's ArrayDeque correctly as a stack or a queue

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

Opening Question

A Fan of Playing Cards

Hold a hand of playing cards in a fan. You can slip a card in at either edge, or pull one out from either edge, but not from the middle. A stack works at one end only. A queue adds at one end, and removes at the other. A deque, pronounced deck, short for double-ended queue, drops the restriction. It can add, remove, and look, at both ends. So it can stand in for a stack or a queue. The puzzle is making all four add and remove operations constant time.

Definition

Deque Operations in Matching Pairs

A deque holds a sequence, from a first element to a last. Its operations come in matching pairs, one for each end. Add first and add last insert. Remove first and remove last take an element out and return it. On an empty deque, Java throws an exception. Peek first and peek last just look. And size and is empty report as usual. A plain array, with the first element pinned at index zero, can't keep up: adding at the front would slide every element one place right.

Implementation

A Doubly Linked Deque with Sentinels

The first design is a doubly linked list. Each node holds a value, a reference to the previous node, and one to the next. Two sentinel nodes, head and tail, sit before the first element and after the last. They never hold data. An empty deque is just the two sentinels, linked to each other. So every real node always has a neighbor on each side, and nothing needs a special case. Both adds are the same action: insert a node between two others. Add first inserts between head and the node after it. Add last inserts between the node before tail, and tail. Insert between rewires four links, and adds one to size. Removing is the mirror image. Unlink checks that the deque isn't empty, then makes a node's two neighbors point at each other. This test adds one and two at the back, then zero and minus one at the front. It removes one element from each end, then empties the deque, and tries one more removal. The lists print from first to last. Minus one leaves the front, two leaves the back, and the last removal throws a no such element exception. Every operation touches a fixed number of references, so each is order one. The price is memory: two extra references per element, and a new node on every add.

Implementation

A Circular Array with a Front Index

The second design is a circular array. Instead of pinning the first element at index zero, let it live anywhere. A variable, front, records its index, and size counts the elements. They occupy size slots in a row from front, wrapping to index zero, as if the array were a ring. Add last writes at front plus size, mod the length. Add first steps front one place backward, and writes there. That backward step adds the length before taking the remainder. In Java, minus one mod four is minus one, not three, so without it the index would go negative.

Growth

Copying in Reading Order

When the array is full, grow builds one twice as large. It copies the elements in reading order, starting from front, and resets front to zero. That straightens out a run that had wrapped around. Copy in plain index order instead, and the elements would come out scrambled.

Trace

A Capacity-Four Deque Wraps and Grows

Follow a deque of capacity four. Add last one, two and three. Front is zero, and one slot is free. Add first nine. Front steps back from zero and wraps to three, so nine sits in the last slot, and the run wraps around to index zero. Remove last returns three. Add last five fills that slot again, and the array is full. Now add last six. Grow doubles the array to eight slots, copies nine, one, two and five in reading order, and resets front to zero.

Quick Check

The Raw Array After Add First

Quick check. This ring has five slots, and starts empty. Add last puts in one and two. Then add first puts in seven, and then eight. The program prints the raw array, where an unused slot shows zero. What does it print? Pause and predict. It prints one, two, zero, eight, seven. Seven steps front back from zero to four, wrapping to the end. Eight steps back again, to three. Nothing moved: one and two never left slots zero and one. Eight, seven, one, two, zero is what a shifting array would hold. And one, two, seven, eight treats add first as if it were add last.

Analysis

Doubling Makes Adds Amortized Constant

One resize copies every element, which looks expensive. But the capacity doubles each time, so resizes are rare. Compare adding at the front of a plain array that shifts. Insert number k moves the k minus one elements already there, so ten thousand inserts make almost fifty million moves. The circular deque, starting at four slots, copies sixteen thousand, three hundred eighty elements in all: under two per add. The copies add up to four, plus eight, plus sixteen, and so on, which is less than twice the final size. So the average cost per add is constant: amortized order one.

Comparison

Linked Deque Versus Circular Array

So both designs give constant-time adds and removes, though the array's adds are amortized. The linked deque spends a node and two references per element, allocating on every add and freeing on removal. The array stores just the value, plus some spare slots. The linked version is known for simple pointer updates, and no resizing. The array is known for compact storage, and fewer allocations.

Key Idea

One Deque as Stack or Queue

Because a deque has every operation of a stack and a queue, it can replace either. The only decision is which end does which job. As a stack, push is add first, pop is remove first, and peek is peek first. What matters is that push and pop use the same end. As a queue, enqueue is add last, and dequeue is remove first: in at one end, out at the other.

Java Library

ArrayDeque and Its Two Spellings

Java ships this structure. Deque is an interface in java dot util, and its everyday implementation is ArrayDeque: a resizable circular array, much like the one just built. This program adds ten, twenty and thirty at the back, and five at the front. It looks at both ends, and polls from both ends. Each job has two spellings. Poll first returns null on an empty deque, while remove first throws a no such element exception. The stack and queue words map onto the same ends: push is add first, offer and add are add last, and poll is poll first.

Key Rule

Why ArrayDeque Refuses Null

ArrayDeque also refuses null. Add last of null throws a null pointer exception, and there's a reason. Poll first and peek first use null to mean empty. A stored null would make the two meanings impossible to tell apart. A few more facts. ArrayDeque isn't safe for several threads at once without extra care, and it has no access by index in the middle. Its documentation says it's likely faster than Stack when used as a stack, and faster than LinkedList when used as a queue. So it's the usual choice for both.

Worked Example

Checking Palindromes from Both Ends

Here's a job only a deque does naturally. A palindrome reads the same forward and backward. Keep only the letters and digits, lowercased, at the back of a deque. Then, while more than one is left, take one from each end, and compare. The loop stops with at most one letter left, which covers both the empty string and the middle letter of an odd-length word. A man, a plan, a canal, Panama is a palindrome. Deque is not. The empty string and a single a both pass, and so does never odd or even.

Common Mistake

Comparing Boxed Characters

One detail matters. Lines ten and eleven copy each removed value into a plain char before comparing. The deque holds boxed Character objects. Compare two of those with not-equals, and Java compares references, not letters. Two boxed characters with the value two hundred are different objects: double equals says false, while equals says true. Small values happen to be shared, so the bug hides until unusual input arrives.

Quick Check

Mixing Push and Add

Quick check. A program pushes one, adds two, pushes three, and adds four, all on one ArrayDeque. Then it prints the deque. What does it show? Pause and predict. It shows three, one, two, four. Push puts an element at the first end, but add puts it at the last end. So the pushes stack up at the front, newest first, and the adds line up at the back. One, two, three, four would need every call to use the same end. Mixing push with add is a classic slip. Pick one end for each job, and stick to it.

Common Mistakes

Deque Pitfalls to Avoid

A few more mistakes to avoid. Calling remove first where poll first was safer, or ignoring a null that poll returned. Letting an index go negative: add the length before the remainder. And copying into a bigger array without realigning to the front. In the linked version, all four links must change on an insert, and size must change on every add and remove.

Key Takeaways

Deque Essentials

To sum up. A deque adds, removes and looks at both ends, so it can act as a stack or a queue. A doubly linked deque with two sentinels makes every operation the same pointer rewiring, in order one. A circular array wraps a front index with the remainder operator, and doubling makes adds amortized order one. And Java's ArrayDeque is that array. It rejects null, because poll and peek use null to mean empty.

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 Adding and Removing at Both Ends of a Sequence

What is a deque in Java?
A deque, pronounced deck and short for double-ended queue, is a sequence that can add, remove, and look at elements at both its first and last ends. In Java, Deque is an interface in java.util with methods such as addFirst, addLast, removeFirst, removeLast, peekFirst, and peekLast. Its everyday implementation is ArrayDeque, a resizable circular array. A deque can act as a stack or a queue.
How does a circular array deque update its front index?
A circular array deque stores a front index and a size, and wraps indexes with the remainder operator. addLast writes at (front + size) % length, and addFirst steps front back with front = (front - 1 + length) % length before writing. Adding the length first matters because in Java, -1 % 4 is -1, not 3, so the index would otherwise go negative and throw an exception.
What is the difference between pollFirst and removeFirst?
Both remove and return the first element of a deque, but they differ when it is empty: pollFirst returns null, while removeFirst throws a NoSuchElementException. Similarly, peekFirst returns null on an empty deque. Because ArrayDeque uses null to mean empty, it refuses null elements, and addLast(null) throws a NullPointerException. Check for null after calling a poll method on a deque that might be empty.
Why do push and add put elements at different ends of an ArrayDeque?
In an ArrayDeque, push is addFirst, while add and offer are addLast, so they work at opposite ends. Pushing 1, adding 2, pushing 3, and adding 4 prints [3, 1, 2, 4], because the pushes stack up at the front, newest first, and the adds line up at the back. Pick one end for each job: as a stack, use push and pop, which share the first end.

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 →